package 题目集.二分;


import org.junit.Test;

/**
 * https://leetcode.cn/problems/median-of-two-sorted-arrays/description/
 */
public class demo05_寻找两个正序数组的中位数 {


    /**
     * 暴力思路：合并数组，然后求中位数
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length + nums2.length];
        int i = 0, l = 0, r = 0;
        while (l < nums1.length && r < nums2.length) {
            if (nums1[l] < nums2[r]) {
                result[i++] = nums1[l++];
            } else {
                result[i++] = nums2[r++];
            }
        }
        while (l < nums1.length) {
            result[i++] = nums1[l++];
        }
        while (r < nums2.length) {
            result[i++] = nums2[r++];
        }
        if (result.length % 2 == 0) {
            return 1.0 *(result[result.length >> 1] + result[(result.length >> 1) - 1])/2;
        } else {
            return result[result.length / 2];
        }
    }

    @Test
    public void test1() {
        int[] a={1,2};
        int[] b={3,4};
        double medianSortedArrays = findMedianSortedArrays(a, b);
        System.out.println(medianSortedArrays);
    }

    /**
     * 思路2：
     * 奇数情况下：
     * 先找出数组a的中点m，然后找a[m]在b中的次序k。设m前面有bef_m个数，m后面有aft_m个数。k前面有bef_k个数，k后面有aft_k个数。
     * 当bef_m+bef_k = aft_m+aft_k时，a[m]就是中位数。
     * 如果bef_m+bef_k > aft_m+aft_k，说明a[m]在b中过大，m需要左移
     * 如果bef_m+bef_k < aft_m+aft_k，说明a[m]在b中过小，m需要右移
     * 而这个移动的过程可以通过二分查找来实现
     */
    int[] a, b;

//    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
//        this.a = nums1;
//        this.b = nums2;
//        /*中位数一定在长的那边*/
//        if (a.length<b.length){
//            int[] temp=a;
//            a=b;
//            b=temp;
//        }
//        int m = a.length / 2;
//
//    }
//
//    /**
//     * 计算bef_m+bef_k-aft_m+aft_k
//     *
//     * @param m
//     * @return
//     */
//    public int findKth(int m) {
//
//    }
}
